package edu.xidian.sei.mlcs;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import edu.xidian.sei.mlcs.util.Logger;
import edu.xidian.sei.mlcs.util.Stopwatch;

/**
 * 通过入度标记每个节点的单项图，所有节点的层级是通过拓扑排序进行设置
 * 
 * @author chaostone
 */
public class LevelGraph {
	private Mlcs mlcs;
	// Location -> Node
	private Map<Location, Node> location2Nodes = new java.util.HashMap<Location, Node>();
	private Set<Location> keyLocs; // 关键点

	private Mlcs.Result result;
	short stepLevel = -1;// 进行步进运算时的深度

	Node start = null; // 起点
	Node end = null; // 终点

	private Logger logger = Logger.getLogger(LevelGraph.class);

	public LevelGraph(Mlcs mlcs) {
		this.mlcs = mlcs;
		start = newNode(mlcs.start);
		end = newNode(mlcs.end);
	}

	public Node get(Location loc) {
		return location2Nodes.get(loc);
	}

	public int size() {
		return location2Nodes.size();
	}

	/**
	 * 向图中添加一个边
	 * 
	 * @return true 如果to没有达到最大层
	 */
	public boolean addEdge(Location start, Location to) {
		Node s = location2Nodes.get(start);
		Node n = location2Nodes.get(to);
		boolean isNewer = false;
		if (null == n) {
			n = newNode(to);
			isNewer = true;
		}
		n.addPredecessor(s, this);
		return isNewer;
	}

	public void addLocation(Location loc) {
		if (!location2Nodes.containsKey(loc))
			newNode(loc);
	}

	public boolean exists(Location loc) {
		return location2Nodes.containsKey(loc);
	}

	/**
	 * 找到关键结点(不包括起点和终点）
	 */
	private void findKeyLocs() {
		long startTime = System.nanoTime();

		keyLocs = new java.util.HashSet<Location>();
		LinkedList<Location> queue = new java.util.LinkedList<Location>();
		int tlevel = 0;
		// 从虚拟终点到该节点的可选路径数，初始终点为1
		Map<Location, BigDecimal> routeCounts = new java.util.HashMap<Location, BigDecimal>();
		routeCounts.put(end.loc, new BigDecimal(1));

		Location queueEnd = mlcs.end;
		// Location nextQuenEnd = null;
		queue.addLast(mlcs.end);

		while (!queue.isEmpty()) {
			Location loc = queue.removeFirst();
			Node node = location2Nodes.get(loc);
			for (Node p : node.predecessors) {
				Location ploc = p.loc;
				if (p.level + tlevel == stepLevel) {
					if (keyLocs.contains(ploc)) {
						routeCounts.put(ploc, routeCounts.get(ploc).add(routeCounts.get(loc)));
					} else {
						keyLocs.add(ploc);
						routeCounts.put(ploc, routeCounts.get(loc));
						// nextQuenEnd = ploc;
						queue.addLast(ploc);
					}
				} else if (p.level + tlevel > stepLevel) {
					collectPredessors(p, stepLevel - tlevel, queue, routeCounts);
				}
			}
			if (loc == queueEnd) {
				if (!queue.isEmpty())
					queueEnd = queue.getLast();
				tlevel += 1;
			}
		}
		keyLocs.remove(start.loc);
		keyLocs.remove(end.loc);
		if (logger.isDebugEnabled()) {
			logger.debug("find key location using " + Stopwatch.format(System.nanoTime() - startTime));
		}
		this.result = new Mlcs.Result(routeCounts.get(start.loc), end.level - 1);
	}

	private void collectPredessors(Node n, int level, LinkedList<Location> queue,
			Map<Location, BigDecimal> routeCounts) {
		if (n.level > level) {
			if (!keyLocs.contains(n.loc)) {
				keyLocs.add(n.loc);
				routeCounts.put(n.loc, new BigDecimal(1));
				for (Node p : n.predecessors) {
					collectPredessors(p, level, queue, routeCounts);
				}
			}
		} else if (n.level == level) {
			if (!keyLocs.contains(n.loc)) {
				queue.add(n.loc);
				routeCounts.put(n.loc, new BigDecimal(1));
				keyLocs.add(n.loc);
			}
		}
	}

	/**
	 * 统计结果
	 */
	public Mlcs.Result stat() {
		findKeyLocs();
		return result;
	}

	/**
	 * 求解关键路径，删除冗余节点
	 */
	public void shrink() {
		long startTime = System.nanoTime();
		findKeyLocs();
		int size = location2Nodes.size();
		// if (size > keyLocs.size() + 2) {
		buildNewMap();
		logger.info("graph shinked, " + (size - location2Nodes.size()) + " removed," + location2Nodes.size()
				+ " reminded. using " + Stopwatch.format(System.nanoTime() - startTime));
		// }
	}

	/**
	 * 根据关键点构建一个新图
	 */
	private void buildNewMap() {
		Map<Location, Node> newLocation2Nodes = new java.util.HashMap<Location, Node>();
		Set<Location> removeKeyLocs = new HashSet<Location>();
		for (Location loc : keyLocs) {
			Node node = location2Nodes.get(loc);
			if (node.level <= stepLevel) {
				newLocation2Nodes.put(loc, node);
			} else {
				removeKeyLocs.add(node.loc);
			}
		}
		keyLocs.removeAll(removeKeyLocs);
		for (Map.Entry<Location, Node> entry : newLocation2Nodes.entrySet()) {
			entry.getValue().reset(keyLocs);
		}
		// 将起点和终点加入map
		newLocation2Nodes.put(mlcs.start, start);
		end.level = (short) (this.stepLevel + 1);
		newLocation2Nodes.put(mlcs.end, end.reset(keyLocs));
		this.location2Nodes = newLocation2Nodes;
	}

	void printState() {
		List<Location> locations = new ArrayList<Location>(location2Nodes.keySet());
		Collections.sort(locations, mlcs.sorter);
		for (Location loc : locations) {
			Node node = location2Nodes.get(loc);
			if (mlcs.end != loc)
				System.out.println(String.valueOf(mlcs.charAt(loc)) + loc + " level:" + node.level);
			else
				System.out.println("end" + loc + " level:" + node.level);
		}
	}

	/**
	 * 打印路径结果
	 */
	public void printPathResult() {
		List<List<Location>> paths = findKeyPaths();
		for (List<Location> path : paths) {
			for (Location l : path)
				System.out.print(mlcs.charAt(l));
			System.out.println();
		}
	}

	public List<List<Location>> findKeyPaths() {
		LinkedList<List<Location>> results = new LinkedList<List<Location>>();
		collectPath(end, new LinkedList<Location>(), results);
		return results;
	}

	private void collectPath(Node n, List<Location> suffix, LinkedList<List<Location>> result) {
		int maxLevel = n.level - 1;
		List<Node> predecessors = new ArrayList<Node>();
		for (Node p : n.predecessors) {
			if (p.level == maxLevel)
				predecessors.add(p);
		}
		for (Node e : predecessors) {
			List<Location> newPaths = new ArrayList<Location>();
			newPaths.add(e.loc);
			newPaths.addAll(suffix);
			Set<Node> eps = e.predecessors;
			if (!eps.isEmpty()) {
				if (eps.contains(start)) {
					result.add(newPaths);
				} else {
					collectPath(e, newPaths, result);
				}
			}
		}
	}

	private Node newNode(Location to) {
		Node n = new Node(to);
		location2Nodes.put(to, n);
		return n;
	}

	// 不要实现equals和hashcode,使用原始的。否则这样会降低在前趋后继的扩充时间开销
	static class Node {
		public Location loc;
		public short level;
		public Set<Node> predecessors = new HashSet<Node>(4);

		public Node(Location loc) {
			this.loc = loc;
		}

		public Node reset(Set<Location> keyLocs) {
			Set<Node> newPredecessors = new HashSet<Node>();
			for (Node p : predecessors) {
				if (p.loc.index[0] == 0 || keyLocs.contains(p.loc)) {
					if (p.level + 1 == this.level)
						newPredecessors.add(p);
				}
			}
			this.predecessors = newPredecessors;
			return this;
		}

		public void addPredecessor(Node predecessor, LevelGraph graph) {
			int newLevel = predecessor.level + 1;
			boolean cascadeLevelUpdated = false;
			if (this.level < newLevel) {
				cascadeLevelUpdated = (this != graph.end);
				this.level = (short) newLevel;
				if (this.level == graph.stepLevel && this != graph.end)
					graph.addEdge(this.loc, graph.mlcs.end);
				// predecessors = new HashSet<Node>();
			}
			predecessors.add(predecessor);
			if (cascadeLevelUpdated)
				this.updateLevelCascade(graph);
		}

		void updateLevelCascade(LevelGraph graph) {
			List<Location> successorLocs = graph.mlcs.nextLocations(this.loc);
			short nextLevel = (short) (this.level + 1);
			boolean findSuccessor = false;
			for (Location successorLoc : successorLocs) {
				Node successor = graph.get(successorLoc);
				if (null != successor) {
					findSuccessor = true;
					successor.predecessors.add(this);
					if (nextLevel > successor.level) {
						successor.level = nextLevel;
						if (successor.level == graph.stepLevel && successor != graph.end)
							graph.addEdge(successor.loc, graph.mlcs.end);
						successor.updateLevelCascade(graph);
					}
				}
			}
			if (!findSuccessor)
				graph.addEdge(this.loc, graph.mlcs.end);
		}

		@Override
		public String toString() {
			return loc + " " + level + " p(" + predecessors.size() + ")";
		}
	}
}
